/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：最长回文子串</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
 * </pre>
 * <p>创建日期：2019年11月22日上午9:51:03</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code05LongestPalindromicSubstring</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code05LongestPalindromicSubstring
{
	public static void main(String[] args)
	{
		/**
		 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
		示例 1：

		输入: "babad"
		输出: "bab"
		注意: "aba" 也是一个有效答案。
		示例 2：

		输入: "cbbd"
		输出: "bb"
		 */
		String palindromic = longestPalindromicSubstring("babsrazwwzazba");
		System.out.println(palindromic);
	}

	/**
	 * 本题采用动态规划思路:
	 * 		当一个子串是回文串时，则该串两端字符相等，且左右两端各去掉一个字符，仍旧是回文串
	 * 		记 dp(i,j)表示给定字符串S为最长回文子串时数组dp值(这里用true/false表示)，i j分别表示子串两端边界在S中的坐标
	 * 		则有：
	 * 			dp(i,j)=(dp(i-1,j+1) && S(i)==S(j))
	 * 		考虑各种情况：
	 * 			dp(i,j):{
	 * 						i-j<=2 && S(i)==S(j) :即子串长度小于2时，只需要判断两端字符是否相等
	 * 						dp(i-1,j+1) && S(i)==S(j)
	 * 					}
	 * 
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(n^2)
	 * 
	 * @param s
	 * @return
	 */
	public static String longestPalindromicSubstring(String s)
	{
		//1.判空
		if (s == null || s.trim().length() <= 0)
		{
			return "";
		}
		//2.取子串默认值
		String str = s.substring(0, 1);
		int len = s.length();
		//3.初始化dp数组
		boolean[][] dp = new boolean[len][len];
		//4.外层循环为子串右端
		for (int i = 0; i < len; i++)
		{
			//5.内层循环为子串左端
			for (int j = 0; j < i; j++)
			{
				//6.如上分析的判断条件
				dp[i][j] = s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[i - 1][j + 1]);
				/**
				 * 7.判断截取
				 * 	1)判断当前坐标内子串是否是回文串
				 *  2)判断当前截取的子串长度是否大于已截取到子串，即控制取到的是最长的回文子串
				 */
				if (dp[i][j] && i - j + 1 > str.length())
				{
					str = s.substring(j, i + 1);
					System.out.println("str的渐变过程：" + str + "====i:" + i + "====j:" + j);
				}
			}
		}
		/**
		 * 循环打印记录数组
		 */
		for (int i = 0; i < dp.length; i++)
		{
			for (int j = 0; j < dp[i].length; j++)
			{
				System.out.print(dp[i][j] + "\t");
			}
			System.out.println("");
		}
		return str;
	}
}
